%error-verbose 
%locations
%token-table
%pure-parser
%name-prefix "vxp_"

%parse-param { void* yyscanner }
%parse-param { struct Node** root }
%parse-param { struct MemBlockInfo* mem }
%lex-param { void* yyscanner }

/* Note: Some rules, such as the "Predicates" rule, do not exist in the 
original specification.  This is the result of adapting the BNF grammar 
to Bison in the following way:

    [BNF]           A::= B Predicate* 

    [Bison]         A: B | B Predicates;
                    Predicates: Predicate | Predicate; 

Such rules are marked with "NonTerminal: BNF->Bison".
*/


%{
    #include <stdio.h>
    #include <stdlib.h>
    #include "tokens.h"
    #include "tokennames.h"
    #include "errors.h"
    #include "vxp-state.h"

    #ifdef DEBUG
        #define YYDEBUG 1
    #endif

	enum yytokentype vxp_lex(YYSTYPE *yylval_param, YYLTYPE *yylloc_param, void* yyscanner);

    #define NAME(x) (TokenNames[(x)-AT_SIGN])
    #define NUMVAL(x) (memNewStringEx(vxp_get_text(yyscanner),vxp_get_leng(yyscanner),mem))

	void* yyscanner;

	extern int vxp_get_leng(void* yyscanner);
	extern char* vxp_get_text(void* yyscanner);
    extern struct vxpState* vxp_get_extra(void* yyscanner);
%}

%token  <t>
        /* Symbols */
        AT_SIGN
        COLON
        COMMA
        DOLLAR_SIGN
        DOT
        DOT_DOT
        DOUBLE_COLON
        LEFT_BRACKET
        LEFT_PAREN
        RIGHT_BRACKET
        RIGHT_PAREN

        /* Operators */
        AND
        DIV
        EQUALS
        GREATER_THAN
        GREATER_THAN_OR_EQUALS
        LESS_THAN
        LESS_THAN_OR_EQUALS
        MINUS
        MOD
        NOT_EQUALS
        OR
        PIPE
        PLUS
        SLASH
        SLASH_SLASH
        MULTIPLY

        /* AXIS */
        ANCESTOR
        ANCESTOR_OR_SELF
        ATTRIBUTE
        CHILD
        DESCENDANT
        DESCENDANT_OR_SELF
        FOLLOWING
        FOLLOWING_SIBLING
        NAMESPACE
        PARENT
        PRECEDING
        PRECEDING_SIBLING
        SELF

        /* Node Type */
        COMMENT
        NODE
        PROCESSING_INSTRUCTION
        TEXT

        /* Stuff */
        NUMBER

        /* NameTest */
        ANY /* As opposed to MULTIPLY */

%token <s>
        LITERAL
        NCNAME

%type <n>
        XPath
        LocationPath
        AbsoluteLocationPath
        RelativeLocationPath
        Step
        AxisSpecifier
        AxisName
        NodeTest
        Predicates
        Predicate
        PredicateExpr
        AbbreviatedAbsoluteLocationPath
        AbbreviatedRelativeLocationPath
        AbbreviatedStep
        Expr
        PrimaryExpr
        FunctionCall
        Arguments
        Argument
        UnionExpr
        PathExpr
        FilterExpr
        OrExpr
        AndExpr
        EqualityExpr
        RelationalExpr
        AdditiveExpr
        MultiplicativeExpr
        UnaryExpr
        NodeType
        FunctionName
        VariableReference
        NameTest
        QName


%initial-action
{
    #ifdef DEBUG
        yydebug=1;
    #endif

    @$.first_line=1;
    @$.first_column=1;
    @$.last_line=1;
    @$.last_column=1;
}

%union
{
    struct Node* n;
    unsigned int t;
    char* s;
}


%start XPath

%%



/********************
* 2. Location Paths *
********************/
XPath:          Expr                                    { *root=newRule(mem,XPath,1,$1); }
            ;

/* This is not the start symbol. See %start */
LocationPath:   RelativeLocationPath                    { $$=newRule(mem,LocationPath,1,$1); $$->extra.isPath=$1->extra.isPath; }
            |   AbsoluteLocationPath                    { $$=newRule(mem,LocationPath,1,$1); $$->extra.isPath=$1->extra.isPath; }
            ;

AbsoluteLocationPath:   SLASH                           { $$=newRule(mem,AbsoluteLocationPath,1,newToken(mem,$1,NAME($1))); $$->extra.isPath=0; }
                    |   SLASH RelativeLocationPath      { $$=newRule(mem,
																AbsoluteLocationPath,
																2,
																newToken(mem,
																			$1,
																			NAME($1)),
																$2); 
														  $$->extra.isPath=1; }
                    |   AbbreviatedAbsoluteLocationPath { $$=newRule(mem,AbsoluteLocationPath,1,$1); $$->extra.isPath=1; }
                    ;

RelativeLocationPath:   Step                            { $$=newRule(mem,RelativeLocationPath,1,$1); $1->extra.isPath=0; }
                    |   RelativeLocationPath SLASH Step { $$=$1; nodeAppendSiblings(mem,$$, 2,  newToken(mem,$2,NAME($2)),
                                                                                            newRule(mem,RelativeLocationPath,1,$3)); 
                                                          $$->extra.isPath=1;
                                                        }
                    |   AbbreviatedRelativeLocationPath { $$=newRule(mem,RelativeLocationPath,1,$1); $$->extra.isPath=1; }
                    ;

/* 2.1 Location Steps */
/* Predicates: BNF->Bison */
Step:                   NodeTest                            { $$=newRule(mem,Step,1,$1);        $$->stepKind=STEP_FORWARD; }
                    |   NodeTest Predicates                 { $$=newRule(mem,Step,2,$1,$2);     $$->stepKind=STEP_FORWARD; }
                    |   AxisSpecifier NodeTest              { $$=newRule(mem,Step,2,$1,$2);     $$->stepKind=$1->stepKind; }
                    |   AxisSpecifier NodeTest Predicates   { $$=newRule(mem,Step,3,$1,$2,$3);  $$->stepKind=$1->stepKind; }
                    |   AbbreviatedStep                     { $$=newRule(mem,Step,1,$1);        $$->stepKind=$1->stepKind; }
                    ;

AxisSpecifier:          AT_SIGN                         { $$=newRule(mem,AxisSpecifier,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_FORWARD; }
                    |   AxisName DOUBLE_COLON           { $$=newRule(mem,AxisSpecifier,2,$1,newToken(mem,$2,NAME($2))); $$->stepKind=$1->stepKind; }
                    ;

/* 2.2 Axes */
AxisName:               ANCESTOR                        { $$=newRule(mem,AxisName,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_REVERSE; }
                    |   ANCESTOR_OR_SELF                { $$=newRule(mem,AxisName,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_REVERSE; }
                    |   ATTRIBUTE                       { $$=newRule(mem,AxisName,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_FORWARD; }
                    |   CHILD                           { $$=newRule(mem,AxisName,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_FORWARD}
                    |   DESCENDANT                      { $$=newRule(mem,AxisName,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_FORWARD}
                    |   DESCENDANT_OR_SELF              { $$=newRule(mem,AxisName,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_FORWARD}
                    |   FOLLOWING                       { $$=newRule(mem,AxisName,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_FORWARD}
                    |   FOLLOWING_SIBLING               { $$=newRule(mem,AxisName,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_FORWARD}
                    |   NAMESPACE                       { $$=newRule(mem,AxisName,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_FORWARD}
                    |   PARENT                          { $$=newRule(mem,AxisName,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_REVERSE; }  
                    |   PRECEDING                       { $$=newRule(mem,AxisName,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_REVERSE; }
                    |   PRECEDING_SIBLING               { $$=newRule(mem,AxisName,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_REVERSE; }
                    |   SELF                            { $$=newRule(mem,AxisName,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_FORWARD}
                    ;

/* 2.3 Node Tests */
NodeTest:               NameTest                                                { $$=newRule(mem,NodeTest,1,$1); }
                    |   NodeType LEFT_PAREN RIGHT_PAREN                         { $$=newRule(mem,NodeTest,3,
                                                                                                        $1,
                                                                                                        newToken(mem,$2,NAME($2)),
                                                                                                        newToken(mem,$3,NAME($3)));
                                                                                }
                    |   PROCESSING_INSTRUCTION LEFT_PAREN RIGHT_PAREN           { $$=newRule(mem,NodeTest,3,
                                                                                                        newToken(mem,$1,NAME($1)),
                                                                                                        newToken(mem,$2,NAME($2)),
                                                                                                        newToken(mem,$3,NAME($3)));
                                                                                }
                    |   PROCESSING_INSTRUCTION LEFT_PAREN LITERAL RIGHT_PAREN   {
                                                                                  $$=newRule(mem,NodeTest,4,
                                                                                                        newToken(mem,$1,NAME($1)),
                                                                                                        newToken(mem,$2,NAME($2)),
                                                                                                        newLiteral(mem,$3,vxp_get_extra(yyscanner)->quoteType),
                                                                                                        newToken(mem,$4,NAME($4)));
                                                                                }
                    ;

/* 2.4 Predicates */
Predicates:             Predicate                                               { $$=newRule(mem,Predicates,1,$1); }
                    |   Predicates Predicate                                    { $$=$1; nodeAppendChild(mem,$$,$2); }
                    ;

Predicate:              LEFT_BRACKET PredicateExpr RIGHT_BRACKET                { $$=newRule(mem,Predicate,3,
                                                                                                        newToken(mem,$1,NAME($1)),
                                                                                                        $2,
                                                                                                        newToken(mem,$3,NAME($3))); }
                    ;

PredicateExpr:          Expr                                                    { $$=newRule(mem,PredicateExpr,1,$1); }
                    ;

/* 2.5 Abbreviated Syntax */
AbbreviatedAbsoluteLocationPath:        SLASH_SLASH RelativeLocationPath        { $$=newRule(mem,AbbreviatedAbsoluteLocationPath,2,newToken(mem,$1,NAME($1)),$2); }
                                    ;

AbbreviatedRelativeLocationPath:        RelativeLocationPath SLASH_SLASH Step   { $$=newRule(mem,AbbreviatedRelativeLocationPath,3,$1,newToken(mem,$2,NAME($2)),$3); }
                                    ;

AbbreviatedStep:                        DOT                                     { $$=newRule(mem,AbbreviatedStep,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_CURRENT; }
                                    |   DOT_DOT                                 { $$=newRule(mem,AbbreviatedStep,1,newToken(mem,$1,NAME($1))); $$->stepKind=STEP_REVERSE; }
                                    ;

/*****************
* 3. Expressions *
*****************/

/* 3.1 Basics */
Expr:                   OrExpr                          { $$=newRule(mem,Expr,1,$1); }
                    ;

PrimaryExpr:            VariableReference               { $$=newRule(mem,PrimaryExpr,1,$1); }
                    |   LEFT_PAREN Expr RIGHT_PAREN     { $$=newRule(mem,PrimaryExpr,3,newToken(mem,$1,NAME($1)),
                                                                                   $2,
                                                                                   newToken(mem,$3,NAME($3)));
                                                        }
                    |   LITERAL                         { $$=newRule(mem,PrimaryExpr,1,newLiteral(mem,$1,vxp_get_extra(yyscanner)->quoteType)); }
                    |   NUMBER                          { $$=newRule(mem,PrimaryExpr,1,newToken(mem,$1,NUMVAL($1))); }
                    |   FunctionCall                    { $$=newRule(mem,PrimaryExpr,1,$1); }
                    ;

/* 3.2 Function Calls */
/* Arguments: BNF->Bison */
FunctionCall:           FunctionName LEFT_PAREN RIGHT_PAREN             { $$=newRule(mem,FunctionCall,3,$1,
                                                                                                        newToken(mem,$2,NAME($2)),
                                                                                                        newToken(mem,$3,NAME($3)));
                                                                        }
                    |   FunctionName LEFT_PAREN Arguments RIGHT_PAREN   { $$=newRule(mem,FunctionCall,4,$1, newToken(mem,$2,NAME($2)),
                                                                                                        $3,
                                                                                                        newToken(mem,$4,NAME($4))); }
                    ;

Arguments:              Argument                        { $$=newRule(mem,Arguments,1,$1); }
                    |   Arguments COMMA Argument        { $$=$1; nodeAppendSiblings(mem,$$->first,2,
                                                                                                newToken(mem,$2,NAME($2)),
                                                                                                $3);
                                                        }
                    ;

Argument:               Expr                            { $$=newRule(mem,Argument,1,$1); }
                    ;

/* 3.3 Node sets */
UnionExpr:              PathExpr
                    |   UnionExpr PIPE PathExpr         { $$=newRule(mem,UnionExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    ;

PathExpr:               LocationPath                                    { $$=newRule(mem,PathExpr,1,$1); $$->extra.isPath=$1->extra.isPath; }
                    |   FilterExpr                                      { $$=newRule(mem,PathExpr,1,$1); $$->extra.isPath=0; }
                    |   FilterExpr SLASH RelativeLocationPath           { $$=newRule(mem,PathExpr,3,$1,newToken(mem,$2,NAME($2)),$3); $$->extra.isPath=1; }
                    |   FilterExpr SLASH_SLASH RelativeLocationPath     { $$=newRule(mem,PathExpr,3,$1,newToken(mem,$2,NAME($2)),$3); $$->extra.isPath=1; }
                    ;

FilterExpr:             PrimaryExpr
                    |   FilterExpr Predicate            { $$=newRule(mem,FilterExpr,2,$1,$2); }
                    ;

/* 3.4 Booleans */
OrExpr:                 AndExpr 
                    |   OrExpr OR AndExpr               { $$=newRule(mem,OrExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    ;

AndExpr:                EqualityExpr
                    |   AndExpr AND EqualityExpr        { $$=newRule(mem,AndExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    ;

EqualityExpr:           RelationalExpr  
                    |   EqualityExpr EQUALS RelationalExpr              { $$=newRule(mem,EqualityExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    |   EqualityExpr NOT_EQUALS RelationalExpr          { $$=newRule(mem,EqualityExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    ;

RelationalExpr:         AdditiveExpr
                    |   RelationalExpr LESS_THAN AdditiveExpr               { $$=newRule(mem,RelationalExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    |   RelationalExpr GREATER_THAN AdditiveExpr            { $$=newRule(mem,RelationalExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    |   RelationalExpr LESS_THAN_OR_EQUALS AdditiveExpr     { $$=newRule(mem,RelationalExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    |   RelationalExpr GREATER_THAN_OR_EQUALS AdditiveExpr  { $$=newRule(mem,RelationalExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    ;

/* 3.5 Numbers */

AdditiveExpr:           MultiplicativeExpr
                    |   AdditiveExpr PLUS MultiplicativeExpr            { $$=newRule(mem,AdditiveExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    |   AdditiveExpr MINUS MultiplicativeExpr           { $$=newRule(mem,AdditiveExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    ;

MultiplicativeExpr:     UnaryExpr
                    |   MultiplicativeExpr MULTIPLY UnaryExpr           { $$=newRule(mem,MultiplicativeExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    |   MultiplicativeExpr DIV UnaryExpr                { $$=newRule(mem,MultiplicativeExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    |   MultiplicativeExpr MOD UnaryExpr                { $$=newRule(mem,MultiplicativeExpr,3,$1,newToken(mem,$2,NAME($2)),$3); }
                    ;

UnaryExpr:              UnionExpr
                    |   MINUS UnaryExpr                 { $$=newRule(mem,UnaryExpr,2,newToken(mem,$1,NAME($1)),$2); }
                    ;

/* 3.7 Lexical Structure */
/* Note: Removed 'processing-instruction' to resolve shift-reduce conflict */
NodeType:               COMMENT                         { $$=newToken(mem,$1,NAME($1)); }
                    |   TEXT                            { $$=newToken(mem,$1,NAME($1)); }
                    |   NODE                            { $$=newToken(mem,$1,NAME($1)); }
                    ;
/* TODO: Make sure it doesn't match NodeType */
FunctionName:           QName                           { $$=newRule(mem,FunctionName,1,$1); }
                    ;

VariableReference:      DOLLAR_SIGN QName               { $$=newRule(mem,VariableReference,2,newToken(mem,$1,NAME($1)),$2); }
                    ;

NameTest:               ANY                             { $$=newRule(mem,NameTest,1,newToken(mem,$1,NAME(MULTIPLY))); }
                    |   QName                           { $$=newRule(mem,NameTest,1,$1); }
                    |   NCNAME COLON ANY                { $$=newRule(mem,NameTest,3,newNCName(mem,$1),
                                                                                newToken(mem,$2,NAME($2)),
                                                                                newToken(mem,$3,NAME(MULTIPLY))); }
                    ;

QName:                  NCNAME                          { $$=newRule(mem,QName,1,newNCName(mem,$1)); }
                    |   NCNAME COLON NCNAME             { $$=newRule(mem,QName,3,newNCName(mem,$1),
                                                                             newToken(mem,$2,NAME($2)),
                                                                             newNCName(mem,$3)); }
                    ;

%%


